package mo.tags.topology;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class L210 {

    private List<List<Integer>> edges;
    private int[] visited;
    private boolean valid = true;
    private List<Integer> res;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        visited = new int[numCourses];
        res = new ArrayList<>();

        for (int[] require : prerequisites) {
            edges.get(require[0]).add(require[1]);
        }

        for (int i = 0; i < numCourses && valid; i++) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }

        if (!valid) {
            return new int[0];
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }


    private void dfs(int index) {
        visited[index] = 1;
        List<Integer> requires = edges.get(index);
        for (int c : requires) {
            if (visited[c] == 0) {
                dfs(c);
            }

            if (!valid) {
                return;
            } else if (visited[c] == 1) {
                valid = false;
                return;
            }
        }
        visited[index] = 2;
        res.add(index);
    }

    public static void main(String[] args) {
        L210 test = new L210();
        System.out.println(Arrays.toString(test.findOrder(2, new int[][]{{1, 0}})));
    }
}
